package array.simple;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 二维网格迁移
 * 输入：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 1
 * 输出：[[9,1,2],[3,4,5],[6,7,8]]
 *
 * 输入：grid = [[3,8,1,9],[19,7,2,5],[4,6,11,10],[12,0,21,13]], k = 4
 * 输出：[[12,0,21,13],[3,8,1,9],[19,7,2,5],[4,6,11,10]]
 *
 * 输入：grid = [[1,2,3],[4,5,6],[7,8,9]], k = 9
 * 输出：[[1,2,3],[4,5,6],[7,8,9]]
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/shift-2d-gri
 */
public class Shift2DGrid {

    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        int[] arr = new int[grid.length * grid[0].length];
        int i = 0;
        for (int[] ints : grid) {
            for (int anInt : ints) {
                arr[i++] = anInt;
            }
        }
        k = k % (grid.length * grid[0].length);
        reverse(arr, 0, arr.length - 1);
        reverse(arr, 0, k - 1);
        reverse(arr, k, arr.length - 1);

        List<List<Integer>> list = new ArrayList<>();
        for (int j = 0; j < arr.length;) {
            List<Integer> li = new ArrayList<>();
            int n = grid[0].length;
            while(n-- > 0)
                li.add(arr[j++]);
            list.add(li);
        }
        return list;
    }

    public void  reverse(int[] nums, int start, int end) {
        while(start < end) {
            int temp = nums[end];
            nums[end] = nums[start];
            nums[start] = temp;
            start += 1;
            end -= 1;
        }
    }

    public static void main(String[] args) {
        Shift2DGrid sf = new Shift2DGrid();
        int[][] arr = {{3,8,1,9},{19,7,2,5},{4,6,11,10},{12,0,21,13}};
        List<List<Integer>> lists = sf.shiftGrid(arr, 4);
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
    }
}
